"""
完美迷宫生成器 - 使用分治法确保唯一路径
使用递归分割算法生成真正的"完美迷宫"（Perfect Maze）
分治策略：将n×n问题分解为4个(n/2)×(n/2)的子问题
"""

import random
import json
import hashlib
from typing import List, Tuple, Dict, Set, Optional
from collections import deque
try:
    from .boss_battle_optimizer import BossBattleOptimizer, optimize_boss_battle
    from .puzzle_solver import PuzzleSolver
except ImportError:
    from boss_battle_optimizer import BossBattleOptimizer, optimize_boss_battle
    from puzzle_solver import PuzzleSolver

class PerfectMazeGenerator:
    """完美迷宫生成器 - 使用分治法保证从起点到终点有且仅有一条路径"""
    
    def __init__(self, size: int):
        if size % 2 == 0:
            size += 1  # 确保是奇数尺寸，便于生成
        self.size = size
        
        # 迷宫矩阵：True=墙壁，False=通路
        self.maze = [[True for _ in range(size)] for _ in range(size)]

        
        # 特殊元素位置
        self.start_pos = None
        self.exit_pos = None
        self.resources = {}
        self.traps = []
        self.locks = []
        self.boss_pos = None
        
        # BOSS战相关
        self.boss_hp = 0
        self.boss_strategy = None
        self.boss_optimizer = None
        
        # 解谜机关相关
        self.puzzle_locks = {}  # {位置: {"password": "123", "clues": [[1,0]], "hash": "...", "cost": 2}}
        
    def generate_maze(self):
        """生成完美迷宫"""
        print(f"开始生成 {self.size}x{self.size} 完美迷宫（递归树分治法）...")
        
        # 使用递归树分治算法生成迷宫
        self._generate_perfect_maze()
        
        # 设置起点和终点
        self._set_start_exit()
        
        # 验证路径唯一性
        self._verify_perfect_maze()
        
        # 放置游戏元素
        self._place_elements()
        
        # 打印统计信息
        self._print_statistics()
        
    def _generate_perfect_maze(self):
        """使用真正的递归树分治算法生成完美迷宫"""
        # 初始化：全部为墙壁
        for i in range(self.size):
            for j in range(self.size):
                self.maze[i][j] = True
                
        # 选择根节点（起点）
        root_x, root_y = 1, 1
        self.maze[root_x][root_y] = False
        
        # 从根节点开始递归构建树
        self._build_recursive_tree(root_x, root_y, set())
        
    def _build_recursive_tree(self, x: int, y: int, visited: set):
        """
        递归构建树状迷宫结构
        每个节点最多有4个子节点（上下左右）
        保证树状结构：任意两点间有且仅有一条路径
        
        参数：
        x, y: 当前节点坐标
        visited: 已访问的节点集合
        """
        visited.add((x, y))
        
        # 四个方向：上、右、下、左
        directions = [(-2, 0), (0, 2), (2, 0), (0, -2)]
        random.shuffle(directions)  # 随机化以增加迷宫多样性
        
        for dx, dy in directions:
            # 计算子节点位置（跳2格确保墙壁厚度）
            child_x = x + dx
            child_y = y + dy
            
            # 检查子节点是否有效
            if (0 < child_x < self.size - 1 and 
                0 < child_y < self.size - 1 and 
                (child_x, child_y) not in visited):
                
                # 连接父节点和子节点（雕刻路径）
                # 这是树的边：从父到子的唯一连接
                wall_x = x + dx // 2
                wall_y = y + dy // 2
                
                self.maze[wall_x][wall_y] = False  # 雕刻连接通道
                self.maze[child_x][child_y] = False  # 雕刻子节点
                
                # 递归处理子节点（分治：子问题）
                self._build_recursive_tree(child_x, child_y, visited)
        
        # 注意：这里不需要连通性修复，因为树结构天然保证：
        # 1. 连通性：从根可达所有节点
        # 2. 无环性：树结构无环路
        # 3. 唯一路径：树中任意两点间路径唯一
        
    def _set_start_exit(self):
        """设置起点和终点"""
        # 起点设在左上角附近的通路
        for i in range(1, self.size):
            for j in range(1, self.size):
                if not self.maze[i][j]:
                    self.start_pos = (i, j)
                    break
            if self.start_pos:
                break
                
        # 终点设在右下角附近的通路
        for i in range(self.size-2, 0, -1):
            for j in range(self.size-2, 0, -1):
                if not self.maze[i][j] and (i, j) != self.start_pos:
                    self.exit_pos = (i, j)
                    break
            if self.exit_pos:
                break
        
    def _verify_perfect_maze(self):
        """验证迷宫是否为完美迷宫（唯一路径）"""
        if not self.start_pos or not self.exit_pos:
            print("✗ 起点或终点未设置")
            return False
            
        # 使用BFS查找路径
        path = self._find_path_bfs(self.start_pos, self.exit_pos)
        
        if not path:
            print("✗ 起点到终点不连通")
            return False
            
        # 验证路径唯一性：临时阻断路径上的一个点，看是否还有其他路径
        if len(path) > 2:
            # 阻断路径中间的一个点
            mid_point = path[len(path) // 2]
            original_state = self.maze[mid_point[0]][mid_point[1]]
            self.maze[mid_point[0]][mid_point[1]] = True
            
            # 尝试寻找替代路径
            alt_path = self._find_path_bfs(self.start_pos, self.exit_pos)
            
            # 恢复原状态
            self.maze[mid_point[0]][mid_point[1]] = original_state
            
            if alt_path:
                print("✗ 发现多条路径，不是完美迷宫")
                return False
                
        print("✓ 验证成功：这是一个完美迷宫（唯一路径）")
        return True
        
    def _find_path_bfs(self, start: Tuple[int, int], end: Tuple[int, int]) -> List[Tuple[int, int]]:
        """使用BFS查找路径"""
        queue = deque([(start, [start])])
        visited = {start}
        
        while queue:
            (x, y), path = queue.popleft()
            
            if (x, y) == end:
                return path
                
            # 探索四个方向
            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nx, ny = x + dx, y + dy
                
                if (0 <= nx < self.size and 0 <= ny < self.size and 
                    not self.maze[nx][ny] and (nx, ny) not in visited):
                    visited.add((nx, ny))
                    queue.append(((nx, ny), path + [(nx, ny)]))
                    
        return []
        
    def _place_elements(self):
        """放置游戏元素"""
        # 找到所有可用的通路位置
        available_positions = []
        for i in range(self.size):
            for j in range(self.size):
                if (not self.maze[i][j] and 
                    (i, j) != self.start_pos and (i, j) != self.exit_pos):
                    available_positions.append((i, j))
                    
        if len(available_positions) < 4:
            return
            
        # 随机选择位置放置元素
        selected = random.sample(available_positions, min(len(available_positions), 8))
        
        # 放置资源
        resource_count = min(3, len(selected) // 3)
        for i in range(resource_count):
            pos = selected[i]
            self.resources[pos] = random.randint(3, 8)
            
        # 放置陷阱
        trap_count = min(2, len(selected) // 4)
        for i in range(resource_count, resource_count + trap_count):
            if i < len(selected):
                self.traps.append(selected[i])
                
        # 放置解谜机关
        lock_count = min(2, len(selected) // 5)
        for i in range(resource_count + trap_count, resource_count + trap_count + lock_count):
            if i < len(selected):
                pos = selected[i]
                self.locks.append(pos)
                # 为每个机关生成解谜内容
                puzzle_data = self._generate_puzzle_for_lock(pos)
                self.puzzle_locks[pos] = puzzle_data
                
        # 放置BOSS
        if resource_count + trap_count + lock_count < len(selected):
            self.boss_pos = selected[resource_count + trap_count + lock_count]
            # 根据迷宫大小设置BOSS血量
            self.boss_hp = self._calculate_boss_hp()
            # 生成BOSS战策略
            self._generate_boss_strategy()
    
    def _generate_puzzle_for_lock(self, pos: Tuple[int, int]) -> Dict:
        """为机关生成解谜内容"""
        # 生成随机3位密码
        password = f"{random.randint(1, 9)}{random.randint(0, 9)}{random.randint(0, 9)}"
        
        # 生成线索
        clues = []
        
        # 随机选择线索类型
        clue_types = random.sample(range(5), random.randint(1, 3))
        
        for clue_type in clue_types:
            if clue_type == 0:  # 素数线索
                clues.append([-1, -1])
            elif clue_type == 1:  # 第1位奇偶性
                first_digit = int(password[0])
                clues.append([1, 0 if first_digit % 2 == 0 else 1])
            elif clue_type == 2:  # 第2位奇偶性
                second_digit = int(password[1])
                clues.append([2, 0 if second_digit % 2 == 0 else 1])
            elif clue_type == 3:  # 第3位奇偶性
                third_digit = int(password[2])
                clues.append([3, 0 if third_digit % 2 == 0 else 1])
            elif clue_type == 4:  # 直接给出某位数字
                digit_pos = random.randint(0, 2)
                digit_val = int(password[digit_pos])
                if digit_pos == 0:
                    clues.append([digit_val, -1, -1])
                elif digit_pos == 1:
                    clues.append([-1, digit_val, -1])
                else:
                    clues.append([-1, -1, digit_val])
        
        # 生成带盐值哈希
        salt = b'\xb2S"e}\xdf\xb0\xfe\x9c\xde\xde\xfe\xf3\x1d\xdc>'
        password_bytes = password.encode('utf-8')
        hash_obj = hashlib.sha256(salt + password_bytes)
        salted_hash = hash_obj.hexdigest()
        
        return {
            "password": password,
            "clues": clues,
            "hash": salted_hash,
            "cost": 2,  # 解锁消耗金币
            "description": f"机关位置{pos}的解谜挑战"
        }
    
    def _calculate_boss_hp(self) -> int:
        """根据迷宫大小计算BOSS血量"""
        # 基础血量 + 迷宫复杂度调整
        base_hp = 40
        size_multiplier = (self.size - 7) // 8  # 每增加8格增加难度
        complexity_hp = size_multiplier * 20
        return base_hp + complexity_hp
    
    def _generate_boss_strategy(self):
        """生成BOSS战斗策略"""
        if not self.boss_pos or self.boss_hp <= 0:
            return
            
        # 估算玩家到达BOSS时的资源（基于收集到的资源）
        estimated_resources = sum(self.resources.values()) + 12  # 基础资源12，确保有足够资源
        
        print(f"\n🎯 生成BOSS战略...")
        print(f"BOSS位置: {self.boss_pos}")
        print(f"BOSS血量: {self.boss_hp}")
        print(f"预估玩家资源: {estimated_resources}")
        
        # 使用BOSS战优化器生成策略
        self.boss_optimizer = BossBattleOptimizer(
            initial_boss_hp=self.boss_hp,
            initial_player_resources=estimated_resources,
            max_rounds=15
        )
        
        result = self.boss_optimizer.branch_and_bound()
        if result:
            skill_sequence, rounds = result
            self.boss_strategy = {
                'skill_sequence': skill_sequence,
                'rounds': rounds,
                'boss_hp': self.boss_hp,
                'estimated_resources': estimated_resources
            }
            print(f"✅ BOSS战略生成成功: {rounds}回合击败")
        else:
            print(f"❌ 无法在规定回合内击败BOSS，建议增加资源或调整难度")
            
    def get_boss_battle_info(self) -> Optional[Dict]:
        """获取BOSS战信息"""
        if not self.boss_pos or not self.boss_strategy:
            return None
            
        return {
            'position': self.boss_pos,
            'hp': self.boss_hp,
            'strategy': self.boss_strategy,
            'recommended_sequence': ' -> '.join(self.boss_strategy['skill_sequence']),
            'min_rounds': self.boss_strategy['rounds']
        }
    
    def simulate_boss_battle(self, player_resources: int) -> Dict:
        """模拟BOSS战斗"""
        if not self.boss_pos:
            return {'success': False, 'message': '迷宫中没有BOSS'}
            
        print(f"\n⚔️ 开始BOSS战斗模拟!")
        print(f"玩家资源: {player_resources}")
        print(f"BOSS血量: {self.boss_hp}")
        
        # 重新优化策略（基于实际玩家资源）
        optimizer = BossBattleOptimizer(
            initial_boss_hp=self.boss_hp,
            initial_player_resources=player_resources,
            max_rounds=15
        )
        
        result = optimizer.branch_and_bound()
        if result:
            skill_sequence, rounds = result
            
            # 详细分析
            analysis = optimizer.analyze_solution(skill_sequence)
            
            return {
                'success': True,
                'skill_sequence': skill_sequence,
                'rounds': rounds,
                'analysis': analysis,
                'message': f'成功在{rounds}回合内击败BOSS!'
            }
        else:
            return {
                'success': False,
                'message': f'玩家资源不足，无法击败BOSS',
                'suggestion': '建议收集更多资源后再挑战BOSS'
            }
    
    def interact_with_lock(self, pos: Tuple[int, int], player_resources: int) -> Dict:
        """与解谜机关交互"""
        if pos not in self.puzzle_locks:
            return {"success": False, "message": "此位置没有解谜机关"}
        
        puzzle = self.puzzle_locks[pos]
        
        if player_resources < puzzle["cost"]:
            return {
                "success": False, 
                "message": f"金币不足！需要{puzzle['cost']}金币，当前只有{player_resources}金币"
            }
        
        print(f"\n🔐 发现解谜机关！位置: {pos}")
        print(f"💰 解锁需要消耗: {puzzle['cost']}金币")
        print(f"🔍 获得线索: {len(puzzle['clues'])}个")
        
        # 显示线索
        for i, clue in enumerate(puzzle['clues']):
            description = self._parse_clue_description(clue)
            print(f"   线索{i+1}: {clue} -> {description}")
        
        # 启动解谜求解器
        try:
            solver = PuzzleSolver()
            
            result = solver.solve_with_salted_hash(puzzle['clues'], puzzle['hash'])
            if result:
                password_str = ''.join(map(str, result))
                return {
                    "success": True,
                    "password": password_str,
                    "cost": puzzle["cost"],
                    "message": f"🎉 解谜成功！密码是: {password_str}",
                    "attempts": solver.search_count
                }
            else:
                return {
                    "success": False,
                    "cost": puzzle["cost"],
                    "message": "❌ 解谜失败，密码破解超时或无解"
                }
        except Exception as e:
            return {
                "success": False,
                "cost": puzzle["cost"],
                "message": f"❌ 解谜过程出错: {e}"
            }
    
    def _parse_clue_description(self, clue: List[int]) -> str:
        """解析线索描述"""
        if len(clue) == 2:
            if clue[0] == -1 and clue[1] == -1:
                return "每位密码为素数且不重复"
            else:
                position = clue[0]
                parity = "偶数" if clue[1] == 0 else "奇数"
                return f"第{position}位是{parity}"
        elif len(clue) == 3:
            for i, digit in enumerate(clue):
                if digit != -1:
                    return f"第{i+1}位是数字{digit}"
        return "未知线索格式"
            
    def get_maze_matrix(self) -> List[List[str]]:
        """获取迷宫矩阵表示"""
        result = []
        for i in range(self.size):
            row = []
            for j in range(self.size):
                pos = (i, j)
                if pos == self.start_pos:
                    row.append('S')
                elif pos == self.exit_pos:
                    row.append('E')
                elif pos in self.resources:
                    row.append('G')
                elif pos in self.traps:
                    row.append('T')
                elif pos in self.locks:
                    row.append('L')
                elif pos == self.boss_pos:
                    row.append('B')
                elif self.maze[i][j]:
                    row.append('#')  # 墙壁
                else:
                    row.append(' ')  # 通路
            result.append(row)
        return result
        
    def print_maze(self):
        """打印迷宫"""
        print("\n生成的完美迷宫（递归树分治法）：")
        maze_matrix = self.get_maze_matrix()
        for row in maze_matrix:
            print(' '.join(row))
            
    def _print_statistics(self):
        """打印统计信息"""
        total_cells = self.size * self.size
        walls = sum(sum(row) for row in self.maze)
        paths = total_cells - walls
        wall_density = walls / total_cells
        
        print(f"\n迷宫统计：")
        print(f"尺寸: {self.size}x{self.size}")
        print(f"总格子数: {total_cells}")
        print(f"墙壁数: {walls}")
        print(f"通路数: {paths}")
        print(f"墙壁密度: {wall_density:.1%}")
        print(f"通路密度: {(1-wall_density):.1%}")
        print(f"资源数量: {len(self.resources)}")
        print(f"陷阱数量: {len(self.traps)}")
        print(f"解谜机关数量: {len(self.locks)}")
        for pos in self.locks:
            if pos in self.puzzle_locks:
                puzzle = self.puzzle_locks[pos]
                print(f"  机关{pos}: 密码{puzzle['password']}, {len(puzzle['clues'])}个线索, 消耗{puzzle['cost']}金币")
        print(f"BOSS位置: {self.boss_pos}")
        if self.boss_pos:
            print(f"BOSS血量: {self.boss_hp}")
            if self.boss_strategy:
                print(f"BOSS战略: {self.boss_strategy['rounds']}回合击败")
                print(f"推荐技能序列: {' -> '.join(self.boss_strategy['skill_sequence'])}")
        
    def save_to_json(self, filename: str):
        """保存到JSON文件"""
        data = {
            'size': self.size,
            'maze': self.get_maze_matrix(),
            'start_pos': self.start_pos,
            'exit_pos': self.exit_pos,
            'resources': {f"{k[0]},{k[1]}": v for k, v in self.resources.items()},
            'traps': [f"{pos[0]},{pos[1]}" for pos in self.traps],
            'locks': [f"{pos[0]},{pos[1]}" for pos in self.locks],
            'puzzle_locks': {
                f"{k[0]},{k[1]}": {
                    'password': v['password'],
                    'clues': v['clues'],
                    'hash': v['hash'],
                    'cost': v['cost'],
                    'description': v['description']
                } for k, v in self.puzzle_locks.items()
            },
            'boss_pos': f"{self.boss_pos[0]},{self.boss_pos[1]}" if self.boss_pos else None,
            'boss_info': {
                'hp': self.boss_hp if self.boss_pos else None,
                'strategy': self.boss_strategy if self.boss_strategy else None,
                'battle_simulation_available': bool(self.boss_pos)
            },
            'algorithm_info': {
                'method': 'recursive_tree_divide_and_conquer',
                'is_perfect': True,
                'wall_density': sum(sum(row) for row in self.maze) / (self.size * self.size),
                'guaranteed_unique_path': True,
                'divide_strategy': 'recursive_tree'
            }
        }
        
        with open(filename, 'w', encoding='utf-8') as f:
            json.dump(data, f, ensure_ascii=False, indent=2)
            
        print(f"完美迷宫已保存到 {filename}")


def generate_perfect_maze(size: int) -> PerfectMazeGenerator:
    """快速生成完美迷宫"""
    generator = PerfectMazeGenerator(size)
    generator.generate_maze()
    return generator


if __name__ == "__main__":
    print("=== 完美迷宫生成器 - 递归树分治法确保唯一路径 ===")
    
    for size in [7, 15]:  # 去掉21，专注优化15x15
        print(f"\n{'='*60}")
        print(f"生成 {size}x{size} 完美迷宫")
        print(f"{'='*60}")
        
        maze = generate_perfect_maze(size)
        maze.print_maze()
        maze.save_to_json(f"perfect_maze_{size}x{size}.json") 